﻿#define _CRT_SECURE_NO_WARNINGS 1
#include "Tree.h"

//申请节点空间
BTNode* buyNode(char x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));

	newnode->data = x;
	newnode->left = newnode->right = NULL;
	return newnode;
}


//创建二叉树
BTNode* createTree()
{
	BTNode* nodeA = buyNode('A');
	BTNode* nodeB = buyNode('B');
	BTNode* nodeC = buyNode('C');
	BTNode* nodeD = buyNode('D');
	BTNode* nodeE = buyNode('E');
	BTNode* nodeF = buyNode('F');

	nodeA->left = nodeB;
	nodeA->right = nodeC;
	nodeB->left = nodeD;
	nodeC->left = nodeE;
	nodeC->right = nodeF;

	return nodeA;
}


//前序遍历---根左右
void PreOrder(BTNode* root)
{
	//如果最开始的根节点就是空，代表没有子树，直接打印空，结束
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	printf("%c ", root->data);
	//根据规则，打印完根节点，对左子树进行前序遍历，递归调用
	PreOrder(root->left);
	//根据规则，遍历完左子树，前序遍历右子树，递归调用
	PreOrder(root->right);
}


//中序遍历---左根右
void InOrder(BTNode* root)
{
	//如果最开始的根节点就是空，代表没有子树，直接打印空，结束
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	//根据规则，先前中遍历左子树
	InOrder(root->left);

	//输出根节点
	printf("%c ", root->data);

	//最后对右子树进行中序遍历
	InOrder(root->right);
}


//后序遍历--左右根
void PostOrder(BTNode* root)
{
	//如果最开始的根节点就是空，代表没有子树，直接打印空，结束
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	//根据规则，先后中遍历左子树
	PostOrder(root->left);

	//遍历完左子树，对右子树进行后序遍历
	PostOrder(root->right);

	//最后，打印根节点
	printf("%c ", root->data);

}


//树的有效节点个数_方法1
//static int size = 0;//定义全局变量
//int BinaryTreeSize(BTNode* root)
//{
//	//根节点为空，即树为空，直接返回结束
//	if(root == NULL)
//	{
//		return 0;
//	}
//
//	//根节点不为空，根节点为有效节点，size+1
//	size++;
//
//	//递归调用左子树、右子树
//	BinaryTreeSize(root->left);
//	BinaryTreeSize(root->right);
//
//	return size;
//
//}


//树的有效节点个数_方法2
//传参
//int BinaryTreeSize(BTNode* root, int* psize)
//{
//	//根节点为空，即树为空，直接返回结束
//	if (root == NULL)
//	{
//		return 0;
//	}
//
//	//根节点不为空，根节点为有效节点，size+1
//	(*psize)++;
//
//	//递归调用左子树、右子树
//	BinaryTreeSize(root->left, psize);
//	BinaryTreeSize(root->right, psize);
//}
//
//

//树的有效节点个数_方法3
//树节点总数 = 1 + 左子树节点个数 + 右子树的节点个数

int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}


//二叉树的叶子节点个数
//总的叶子节点个数 = 左子树叶子节点树 + 右子树叶子节点数
int BinaryTreeLeafSize(BTNode* root)
{
	//判断整体的根节点
	if (root == NULL)
	{
		return 0;
	}

	//叶子节点条件，左右子节点均为NULL
	if (root->left == NULL && root->right == NULL)
	{
		return 1;//叶子节点数+1
	}

	//否则继续遍历子树
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}


//求第k层节点个数
//第k层节点个数 = 左子树第k层节点个数 + 右子树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	//判断整体根节点
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	//否则递归遍历子树
	return BinaryTreeLevelKSize(root->left, k-1) + BinaryTreeLevelKSize(root->right, k-1);
}


//求树的深度/高度
int BinaryTreeDepth(BTNode* root)
{
	//判断根节点
	if (root == NULL)
	{
		return 0;
	}

	//提前保存子树高度
	int leftDeptt = BinaryTreeDepth(root->left);
	int rightDeptt = BinaryTreeDepth(root->right);

	return 1 + (leftDeptt > rightDeptt ? leftDeptt : rightDeptt);
}


// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	//进行匹配
	if (root->data == x)
	{
		return root;
	}
	//保存左子树遍历结果
	BTNode* leftFind = BinaryTreeFind(root->left, x);
	//若为空，可能在右子树
	if (leftFind)
	{
		return leftFind;
	}
	//保存右子树遍历结果
	BTNode* rightFind = BinaryTreeFind(root->right, x);
	//若为空，节点不存在
	if (rightFind)
	{
		return rightFind;
	}
	return NULL;
}


// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	BinaryTreeDestory(&((*root)->left));
	BinaryTreeDestory(&((*root)->right));
	free(*root);
	*root = NULL;
}


// 层序遍历---借助数据结构：队列
//void LevelOrder(BTNode* root)
//{
//	Queue q;
//	QueueInit(&q);
//	QueuePush(&q, root);
//	while (!QueueEmpty(&q))
//	{
//		//取队头，打印队头
//		BTNode* top = QueueFront(&q);
//		printf("%c ", top->data);
//		QueuePop(&q);
//		//队头节点不为空的孩子节点入队列
//		if (top->left)
//			QueuePush(&q, top->left);
//		if (top->right)
//			QueuePush(&q, top->right);
//	}
//
//	QueueDesTroy(&q);
//}


// 判断⼆叉树是否是完全⼆叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	//头节点入队列
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取队头，出队头
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		if (top == NULL)
		{
			//top取到空就直接出队列
			break;
		}
		//将队头节点的左右孩子入队列
		QueuePush(&q, top->left);
		QueuePush(&q, top->right);
	}
	//队列不为空，继续取队列中的队头
	while (!QueueEmpty(&q))
	{
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		if (top != NULL)
		{
			//不是完全二叉树
			QueueDesTroy(&q);
			return false;
		}
	}
	QueueDesTroy(&q);
	return true;
}